package ljl.alg.wangzheng_camp.round1.find_the_law;

import java.util.HashSet;
import java.util.Set;

public class _01_08_set_zeroes {
    /**
     * 不能发现一个处理一行，会把原来的 0 覆盖了，所以得先找
     * 找全了再清零
     * <p>
     * 0 1 1
     * 1 0 1
     * 1 1 1
     * <p>
     * 我打算这么搞：找两个集合（set），一个存行，一个存列
     * 如果发现有 0，那它那个行列号记录
     * 最后再挨个行列清零
     * <p>
     * 感觉有点笨逼啊
     * <p>
     * 过是过了，好像效率不高
     */
    public void setZeroes1(int[][] matrix) {
        if (matrix.length == 0) return;
        int m = matrix.length, n = matrix[0].length;
        
        // 这可以不用 set，用两个 boolean 数组可能更快
        Set<Integer> rows = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rows.contains(i) || cols.contains(j))
                    matrix[i][j] = 0;
            }
        }
    }
    
    /**
     * 猥琐男使用第一行和第一列代替了上面那个两个集合
     * 然后用两个变量记录第一行第一列是否有 0，如果有也要清除
     * <p>
     * 可以看到，又臭又长，但是会快一点
     */
    public void setZeroes2(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // 准备数据需要好多行
        boolean firstRowHas0 = false, firstColHas0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColHas0 = true;
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                firstRowHas0 = true;
                break;
            }
        }
        // 记录每行每列是否有 0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0)
                    matrix[0][j] = matrix[i][0] = 0;
            }
        }
        // 清空数据
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        }
        // 清空第一行第一列
        if (firstColHas0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (firstRowHas0) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
    }
    
    /**
     * 我们可以对方法二进一步优化，只使用一个标记变量记录第一列是否原本存在 0
     * 这样，第一列的第一个元素即可以标记第一行是否出现 0
     * 但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素
     */
    public void setZeroes3(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // 省了一个变量，目前不知道第一行该不该置零
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            // 知道了第一列是不是该置零
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
            // 第一行从第二个元素开始找，如果后面有 0 会存到 [0][0] 元素里
            // [0][0] 是漏网之鱼，它就是隐藏的 flagRow0
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 如果正着遍历，第一行的更新会把所有列标记都清零，导致所有列都空了
        // 但是如果倒着来，后面的行不影响前面的行
        // 最后根据第一行第一个元素，把第一行全清空
        for (int i = m - 1; i >= 0; i--) {
            // 第一列第一个元素是标记，不能更新
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            // 第一列是否更新根据标记位判断，第一列是元数据
            if (flagCol0) {
                matrix[i][0] = 0;
            }
        }
    }
}
